package com.fr.lintcode.dp;

import org.junit.Test;

/**
*作者：furong
*日期：2017年3月22日
*时间：下午5:02:06
*/
public class Q125 {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int V[]) {
        if (m <= 0 || A == null || V == null || A.length <= 0 || V.length <= 0) {
            return 0;
        }
        int dp[][] = new int[A.length + 1][m + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= A.length; j++) {
                if (i < A[j - 1]) {
                    dp[j][i] = dp[j - 1][i];
                } else if (dp[j - 1][i] < dp[j - 1][i - A[j - 1]] + V[j - 1]) {
                    dp[j][i] = dp[j - 1][i - A[j - 1]] + V[j - 1];
                } else {
                    dp[j][i] = dp[j - 1][i];
                }
            }
        }
        return dp[A.length][m];
    }

    @Test
    public void testA() {
        int m = 10;
        int A[] = { 2, 3, 5, 7 };
        int V[] = { 1, 5, 2, 4 };
        System.out.println(backPackII(m, A, V));
    }
}
